package Tree116;
import java.util.*;

public class IsSymmtricalTree {
     static class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
 }
 //第一种方法
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if(pRoot==null){
            return true;
        }
        Stack<TreeNode> s1=new Stack<>();
        Stack<TreeNode> s2=new Stack<>();
        TreeNode cur=pRoot;
        s1.push(cur.left);//左右根节点先入栈
        s2.push(cur.right);
        while(!s1.isEmpty()&&!s2.isEmpty()){
            TreeNode cur1=s1.pop();//分别弹出左边节点和右边节点比较
            TreeNode cur2=s2.pop();
            if(cur1==null&&cur2==null){ //左右节点为空时跳过
                continue;
            }
            if(cur1==null||cur2==null){//左节点为空右节点不为空或左节点不为空右节点为空则一定不对称
                return false;
            }
            if(cur1.val!=cur2.val){
                return false;
            }
            s1.push(cur1.left);//层次遍历，左树左等于右树右，左树右等于右树左，分别入栈若满足条件，则为对称树
            s2.push(cur2.right);
            s1.push(cur1.right);
            s2.push(cur2.left);
        }
        return s1.isEmpty()&&s2.isEmpty();//若两个栈都为空则返回true
    }
    //第二种方法
    public boolean way1(TreeNode cur1,TreeNode cur2){
         if(cur1==null&&cur2==null){//节点为空为真
             return true;
         }
         if(cur1==null||cur2==null||cur1.val!=cur2.val){//其中一节点为空或两值不相等就一定不对称
             return false;
         }
         return way1(cur1.left,cur2.right)&&way1(cur1.right,cur2.left);//一层一层的比较
    }
    public boolean way2(TreeNode pRoot){
         return way1(pRoot,pRoot);
    }

}
